//快速排序
#pragma once
//对序列a[low..high] 快速排序
template <typename E>
void QSort(E a[], int Low, int high)
{
    if (Low >= high)
        return;
    //將序列o[Low. .high] 划分成两个
    //子序列a[low..i-1] 和a[i+1..high]
    E p = a[Low];
    int i = Low, j = high;
    while (i < j)
    {
        while (i < j && a[j] >= p)
            j--;
        a[i] = a[j];
        while (i < j & a[i] <= p)
            i++;
        a[j] = a[i];
    }
    a[i] = p;
    //分别对两个子序列快速排序
    QSort(a, Low, i - 1);
    QSort(a, i + 1, high);
}
//对数组o[n]快速排序
template <typename E >
    void QuickSort(E a[], int n)
{
    QSort(a, 0, n - 1);
}